package com.zp.self.module.编程测试;

import org.junit.Test;

/**
 * @author By ZengPeng
 * @Description
 * @date in  2021/4/9 9:46
 * @Modified By
 */
public class 斐波拉切数 {

    @Test
    public  void  feiBoLaQieTest(){
        System.out.println(feiBoLaQie_0(0));
        System.out.println(feiBoLaQie_0(1));
        System.out.println(feiBoLaQie_0(2));
        System.out.println(feiBoLaQie_0(3));
        System.out.println(feiBoLaQie_0(4));
        System.out.println(feiBoLaQie_0(5));

        //System.out.println(feiBoLaQie_0(50));//递归：50算不出来了,底层栈调用太多了--

        long start = System.nanoTime();
        System.out.println(feiBoLaQie_1(1000)+"--数组耗时："+(System.nanoTime()-start));//数组能计算，但稍微慢点

        long end1 = System.nanoTime();
        System.out.println(feiBoLaQie_2(1000)+"--变量耗时："+(System.nanoTime()-end1));//变量的形式更快
    }

    //动态规划：变量记录方式
    private long feiBoLaQie_2(int n) {
        if(n<2)
            return n;
        long a=0,b=1,middle;
        while(n-->1){
            middle = b;
            b = a+b;
            a=middle;
        }
        return b;
    }
    //数组记录
    private long feiBoLaQie_1(int i) {
        if(i<2)
            return i;
        long[] arr = new long[i+1];
        arr[0]=0; arr[1]=1;
        for (int j = 2; j <= i; j++) {
            arr[j]=arr[j-1]+arr[j-2];
        }
        return arr[i];
    }

    //递归方式  --斐波拉契数递归到43就会很慢
    //-- 频繁的函数调用、没有有效的使用中间结果都会导致效率的下降
    private long feiBoLaQie_0(int i) {
        if(i==0 || i==1)
            return i;
        else
            return feiBoLaQie_0(i-1)+feiBoLaQie_0(i-2);
    }
}
